constexpr int BASE = 100000000;
constexpr int MAX_LENGTH = 1000;
constexpr int NUM_DIGIT = 8;
i64 mul_mod (i64 x, i64 y, i64 n){
	i64 T = std::floor(std::sqrt(n) + 0.5);
	i64 t = T * T - n;
	i64 a = x / T; i64 b = x % T;
	i64 c = y / T; i64 d = y % T;
	i64 e = a * c / T; i64 f = a * c % T;
	i64 v = ((a * d + b * c) % n + e * t) % n;
	i64 g = v / T; i64 h = v % T;
	i64 ans = (((f + g) * t % n + b * d) % n + h * T) % n;
	while (ans < 0) {
		ans += n;
	}
	return ans;
}
struct BigInt {

	BigInt(const char* str = "0") {
		(*this) = str;
	}

	BigInt operator=(const char* str) {
		int j = std::strlen(str) - 1;
		len = j / NUM_DIGIT + 1;
		for(int i = 0; i <= len; i++) {
			s[i] = 0;
		}
		for(int i = 0; i <= j; i++) {
			int k = (j - i) / NUM_DIGIT + 1;
			s[k] = s[k] * 10 + (str[i] - '0');
		}
		return *this;
	}

	void print() {
		printf("%d", s[len]);
		for(int i = len - 1; i >= 1; i--) {
			printf("%0*d", NUM_DIGIT, s[i]);
		}
	}

	int len;
	int s[MAX_LENGTH];
};

// > return > 0
// < return < 0
// = return = 0
int compare(const BigInt &lhs, const BigInt &rhs) {
	if(lhs.len > rhs.len) {
		return 1;
	}
	if(lhs.len < rhs.len) {
		return -1;
	}
	int cur = lhs.len;
	while((cur > 1) && (lhs.s[cur] == rhs.s[cur])) {
		cur--;
	}
	return lhs.s[cur] - rhs.s[cur];
}

bool operator<(const BigInt &lhs, const BigInt &rhs) {
	return compare(lhs, rhs) < 0;
}

bool operator<=(const BigInt &lhs, const BigInt &rhs) {
	return compare(lhs, rhs) <= 0;
}

bool operator>(const BigInt &lhs, const BigInt &rhs) {
	return compare(lhs, rhs) > 0;
}

bool operator>=(const BigInt &lhs, const BigInt &rhs) {
	return compare(lhs, rhs) >= 0;
}

bool operator==(const BigInt &lhs, const BigInt &rhs) {
	return compare(lhs, rhs) == 0;
}

bool operator!=(const BigInt &lhs, const BigInt &rhs) {
	return compare(lhs, rhs) != 0;
}


BigInt operator+(const BigInt &lhs, const BigInt &rhs) {
	BigInt ret;
	int i;
	for(i = 1; i <= lhs.len || i <= rhs.len || ret.s[i]; i++) {
		if(i <= lhs.len) {
			ret.s[i] += lhs.s[i];
		}
		if(i <= rhs.len) {
			ret.s[i] += rhs.s[i];
		}
		ret.s[i + 1] = ret.s[i] / BASE;
		ret.s[i] %= BASE;
	}
	ret.len = i - 1;
	if(ret.len == 0) {
		ret.len = 1;
	}
	return ret;
}

// lhs > rhs
BigInt operator-(const BigInt &lhs, const BigInt &rhs) {
	BigInt ret;
	for(int i = 1, j = 0; i <= lhs.len; i++) {
		ret.s[i] = lhs.s[i] - j;
		if(i <= rhs.len) {
			ret.s[i] -= rhs.s[i];
		}
		if(ret.s[i] < 0) {
			j = 1;
			ret.s[i] += BASE;
		} else {
			j = 0;
		}
	}
	ret.len = lhs.len;
	while(ret.len > 1 && !ret.s[ret.len]) {
		ret.len--;
	}
	return ret;
}

BigInt operator*(const BigInt &lhs, const BigInt &rhs) {
	BigInt ret;
	i64 g = 0;
	ret.len = lhs.len + rhs.len;
	ret.s[0] = 0;
	for(int i = 1; i <= ret.len; i++) {
		ret.s[i] = 0;
	}
	for(int k = 1; k <= ret.len; k++) {
		i64 tmp = g;
		int j = k + 1 - rhs.len;
		if(j < 1) {
			j = 1;
		}
		for(; j <= k && j <= lhs.len; j++) {
			tmp += (i64)lhs.s[j] * (i64)rhs.s[k + 1 - j];
		}
		g = tmp / BASE;
		ret.s[k] = tmp % BASE;
	}
	while(ret.len > 1 && !ret.s[ret.len]) {
		ret.len--;
	}
	return ret;
}
BigInt operator/(const BigInt &lhs, int num) {
	i64 g = 0;
	BigInt ret;
	ret.len = lhs.len;
	for(int i = lhs.len; i > 0; i--) {
		i64 tmp = g * BASE + lhs.s[i];
		ret.s[i] = tmp / num;
		g = tmp % num;
	}
	while(ret.len > 1 && ! ret.s[ret.len]) {
		ret.len--;
	}
	return ret;
}
BigInt operator/(const BigInt &lhs, const BigInt &rhs) {
	BigInt l = "0", r = lhs;
	while(l < r) {
		BigInt m = l + (r - l + "1") / 2;
		if(m * rhs <= lhs) {
			l = m;
		} else {
			r = m - "1";
		}
	}
	return l;
}

i64 BigMod(const BigInt &a, i64 m) {
	i64 d = 0;
	for(int i = a.len; i > 0; i--) {
		d = mul_mod(d, BASE, m);
		d = (d + a.s[i]) % m;
	}
	return d;
}
BigInt sqrt(const BigInt &a) {
	BigInt x, y = a;
	do {
		x = y;
		y = (x + a / x) / 2;
	}while(y < x);

	return x;
}
BigInt gcd(BigInt a, BigInt b) {
	BigInt c = "1";
	while(true) {
		if(a == b) {
			return a * c;
		} else if(a.s[1] % 2 == 0 && b.s[1] % 2 == 0) {
			a = a / 2;
			b = b / 2;
			c = c * "2";
		} else if(a.s[1] % 2 == 0) {
			a = a / 2;
		} else if(b.s[1] % 2 == 0) {
			b = b / 2;
		} else if(b < a) {
			a = a - b;
		} else {
			b = b - a;
		}
	}
}